package _2022.hot100._22_括号生成;

import java.util.ArrayList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-01 15:09
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuffer combination = new StringBuffer();
        int c = 0, cSum = 0, index = 0;
        backTrace(res, n, c, cSum, index, combination);
        return res;
    }

    public void backTrace(List<String> res, int n, int c, int cSum, int index, StringBuffer combination) {
        if (index == 2 * n) {
            res.add(combination.toString());
        } else {
            if (c == 0 && cSum < n) {
                combination.append('(');
                backTrace(res, n, c+1, cSum+1, index + 1, combination);
            } else if (c != 0 && cSum < n) {
                combination.append('(');
                backTrace(res, n, c + 1, cSum + 1, index + 1, combination);
                combination.delete(index,combination.length());

                combination.append(')');
                backTrace(res, n, c - 1, cSum, index + 1, combination);

            } else if (c == 0 && cSum == n) {
                combination.append(')');
                backTrace(res, n, c, cSum, index + 1, combination);
            } else if (c != 0 && cSum == n) {
                combination.append(")");
                backTrace(res, n, c, cSum, index + 1, combination);
            }
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.generateParenthesis(3).toString());
    }
}
